Lowest common ancestor (LCA) of a binary tree

Time: O(N); Space: O(H); medium

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia:

“The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = {TreeNode} [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: {TreeNode} [3]

Explanation:

  • The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = {TreeNode} [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: {TreeNode} [5]

Explanation:

  • The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Notes:

  • All of the nodes’ values will be unique.

  • p and q are different and both values will exist in the binary tree.

[13]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[14]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: int
        :type q: int
        :rtype: TreeNode
        """
        # Base Case
        if root is None:
            return None

        # If either n1 or n2 matches with root's key, report
        #  the presence by returning root (Note that if a key is
        #  ancestor of other, then the ancestor key becomes LCA
        if root.val == p or root.val == q:
            return root

        # Look for keys in left and right subtrees
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)

        # If both of the above calls return Non-NULL, then one key
        # is present in once subtree and other is present in other,
        # So this node is the LCA
        if left_lca and right_lca:
            return root

            # Otherwise check if left subtree or right subtree is LCA
        return left_lca if left_lca is not None else right_lca

[15]:

s = Solution1()

root = TreeNode(3)
root.left, root.right = TreeNode(5), TreeNode(1)
root.left.left, root.left.right = TreeNode(6), TreeNode(2)
root.right.left, root.right.right = TreeNode(0), TreeNode(8)
root.left.right.left, root.left.right.right = TreeNode(7), TreeNode(4)
p = 5
q = 1
res = s.lowestCommonAncestor(root, p, q)
assert res.val == 3

root = TreeNode(3)
root.left, root.right = TreeNode(5), TreeNode(1)
root.left.left, root.left.right = TreeNode(6), TreeNode(2)
root.right.left, root.right.right = TreeNode(0), TreeNode(8)
root.left.right.left, root.left.right.right = TreeNode(7), TreeNode(4)
p = 5
q = 4
res = s.lowestCommonAncestor(root, p, q)
assert res.val == 5